package com.wdc.回溯;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

@SuppressWarnings("all")
public class E11Leetcode46 {
    private List<List<Integer>> result = new ArrayList<>();
    private LinkedList<Integer> path = new LinkedList<>();
    private boolean used[];
    public List<List<Integer>> permute(int[] nums) {

        used = new boolean[nums.length];

//        backtracking(nums,path);
        premutebacking(nums,used);
        return result;

    }

    void backtracking(int[] nums,LinkedList<Integer> path){
        if (path.size() == nums.length){
            result.add(new ArrayList<>(path));
        }

        //循环宽度 ,因为可以按任意序列返回，所以不用staartIndex
        for (int i = 0; i < nums.length; i++) {
            //每次从 0 开始，所以需要判断 path 中是否包含了当前元素
            if (path.contains(nums[i])){
                continue;
            }
            path.add(nums[i]);
            backtracking(nums,path);
            path.removeLast();

        }

    }

    void premutebacking(int[] nums , boolean[] used){
        if (path.size() == nums.length){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]){
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            premutebacking(nums,used);
            used[i] = false;
            path.removeLast();

        }

    }

    public static void main(String[] args) {
        int[] nums = {1,2,3};
        E11Leetcode46 e11Leetcode46 = new E11Leetcode46();
        System.out.println(e11Leetcode46.permute(nums));
    }


}
